Jaga-ja-valitse algoritm

Jaga-ja-valitse algoritmid on klass algoritme arvutiteaduses mis põhinevad mitmeharulisel rekursioonil. Jaga-ja-valitse algoritmid põhinevad probleemi kaheks või rohkemaks sarnaseks alamprobleemiks jagamisel, kuni need muutuvad piisavalt lihtsaks, et otseselt lahendada. Seejärel alamprobleemide lahendid kombineeritakse, et saada algse probleemi lahend.

See tehnika on alus efektiivsetele algoritmitele erinevate probleemide jaoks, näiteks sortimine (kiirsortimine, mestimissortimine), suurte arvude korrutamine (Karatsuba algoritm), lähima punktipaari leidmine ja lauseanalüüs.

Jaga-ja-valitse algoritmide põhimõte on sarnane matemaatilise induktsiooniga; viimane on ka viis nende algoritmide korrektsuse tõestamiseks. Jaga-ja-valitse algoritmide algoritmilist keerukust määratakse sageli rekurentsusseoste arvutamise teel.

Jaga-ja-valitse

Nime "jaga-ja-valitse" kasutatakse mõnikord algoritmide kohta, mis jagab iga probleemi vaid üheks alamprobleemiks, näiteks kahendotsingu algoritm sorditud loendis kirje leidmiseks^[1]. Neid algoritme saab implementeerida efektiivsemalt kui jaga-ja-valitse algoritme üldiselt; täpsemalt, kui need kasutavad sabarekursiooni, saab neid teisendada lihtsateks tsükliteks. Sellise laia definitsiooni korral aga võiks iga algorirmi, mis kasutab rekursiooni või tsükleid lugeda jaga-ja-valitse algoritmideks. Seetõttu osad autorid arvavad, et nime "jaga-ja-valitse" peaks kasutama vaid siis, kui iga probleem võib jaguneda kaheks või rohkemaks alamprobleemiks^[2]. Ühe alamjuhuga klassi nimeks pakutakse "vähenda-ja-valitse."^[3]

Oluline rakendus jaga-ja-valitse algoritmidele on optimeerimine, kus, kui igal sammul otsinguruumi vähendatakse (pügatakse) konstantse teguri korda, siis algoritmil üldiselt on sama asümptootiline keerukus kui pügamissammul; keerukuse konstant sõltub pügamistegurist. Sellist algoritmi tuntakse ka kui püga-ja-jaga algoritmi.

Varajased ajaloolised näited

Varajased näited on peamiselt vähenda-ja-valitse: algprobleem vähendatakse üheks alamprobleemiks, ja on lahendatava iteratiivselt.

Kahendotsingul, kus alamprobleemid on ligikaudu pool algsest probleemist, on pikk ajalugu. Kuigi selge kirjeldus sellest algoritmist arvutitele avaldati 1946. aastal John Mauchly artiklis, siis idee sorteeritud loendite kasutamisest otsimise lihtsustamiseks on pärit hiljemalt Babülooniast 200 aastat eKr^[4]. Veel üks varajane näide on Eukleidese algoritm suurima ühisteguri leidmiseks, mis jääb ajaliselt mitu sajandit eKr.

Eelised

Keeruliste probleemide lahendamine

Jaga-ja-valitse algoritmid on võimas tööriist ideeliselt keeruliste probleemide lahendamiseks: vaja on vaid viise probleemi alamprobleemideks jagamiseks, lihtsate juhtude lahendamiseks ja alamprobleemide lahendite kombineerimiseks. Sarnaselt, vähenda-ja-valitse vajab vaid probleemi üheks lihtsamaks alamjuhuks vähendamist, näiteks klassikalise Hanoi torni probleemi korral vähendatakse torni kõrgusega $n$ liigutamine torni kõrgusega $n-1$ liigutamiseks.

Algoritmi efektiivsus

Jaga-ja-valitse lähenemine sageli aitab leida kiireid algoritme. See oli võtmetähtsusega näiteks Karatsuba kiire korrutamise meetodi, kiirsortimise ja mestimissortimise, Strasseni algoritmi maatriksite korrutamise ja kiirete Fourier' teisenduste jaoks.

Kõikides nendes juhtudes viis jaga-ja-valitse lähenemise kasutamine parema asümptootilise keerukuseni. Näiteks, kui

baasjuhul on konstandiga piiratud suurus
töö probleemi alamprobleemideks jagamiseks ja lahendite kombineerimiseks on lineaarselt sõltuv probleemi suurusest $n$
Leidub piiratud arv $p$ alamprobleeme suurusega $\sim {\frac {n}{p}}$

siis selle jaga-ja-valitse algoritmi keerukus on ${\mathcal {O}}(n\log _{p}n)$ .

Paralleelsus

Jaga-ja-valitse algoritmid on loomupäraselt sobilikud paralleelarvutuseks,eriti jagatud mäluga süsteemides, kus andmevahetust protsessorite vahel ei ole vaja ette plaanida, sest eri alamprobleeme saab lahendata rööbiti.

Mälukasutus

Jaga-ja-valitse algoritmid loomupäraselt kipuvad efektiivselt kasutama protsessori vahemälusid, sest kui alamprobleem on piisavalt väike, siis selle ja kõik selle alamprobleemid saab, põhimõtteliselt, lahendada vahemälus, kasutamata aeglast põhimälu. Algoritmid, mis on disainitud kasutama vahemälu sel viisil, on vahemälu suurusest sõltumatud.^[5] Lisaks saab jaga-ja-valitse algoritme oluliste probleemide jaoks (näiteks sortimine) disainida olema vahemälu suurusest sõltumatult optimaalsed: nad kasutavad vahemälu tõenäosuslikult optimaalsel viisil, asümptootilises tähenduses, sõltumata vahemälu suurusest. Vastupidi, traditsiooniline lähenemine vahemälu kasutamisele on tükeldamine, kus probleem jagatakse sobiva suurusega tükkideks – ka see kasutab vahemälu optimaalselt, kuid vaid siis, kui algoritm on optimeeritud antud masina spetsiifilisele vahemälu suurusele.

Sama eelis kehtib ka muude hierarhiliste hoiusüsteemide korral, nagu näiteks NUMA ja virtuaalmälu, ning ka mitme vahemälu taseme korral: kui alamprobleem on piisavalt väike, saab seda lahendada antud hierarhiataseme sees, puutumata kõrgemaid (aeglasemaid) tasemeid.

Ümardamine

Arvutustes, kus kasutatakse ümardamist, näiteks ujukomaarvudega, võib jaga-ja-valitse algoritm anda täpsemaid tulemusi kui pealtnäha samaväärne iteratiivne algoritm. Näiteks, N arvu saab kokku liita kas lihtsa tsükliga, mis liidab iga andmepunkti ühele summamuutujale, või jaga-ja-valitse kaskaadliitmise algoritmiga, mis jagab andmed kaheks pooleks, rekursiivselt arvutab mõlema summa ja siis liidab need summad kokku. Kuigi teine algoritm teeb sama palju arvutusi kui teine, ja on rekursiooni tõttu aeglasem, on see tavaliselt täpsem.^[6]

Implementeerimine

Rekursioon

Jaga-ja-valitse algoritmide loomulik implementatsioon on rekursiooniga. Sel juhul parajasti lahendatava alamprobleemi ülemprobleemid hoitakse automaatselt kutsepinus.

Eraldi pinu

Jaga-ja-valitse algorime saab implementeerida ka mitte-rekursiivse programmiga, mis hoiab osalisi alamprobleeme mõnes eraldi andmestruktuuris, nagu näiteks pinus või riviloendis (queue). See lähenemine lubab rohkem valikut järgmise alamprobleemi valimisel, mis on osade rakenduste, nagu näiteks laiuti otsingu, korral oluline. See on ka standardne lähenemine programmeerimiskeeltes, mis ei toeta rekursiooni.

Pinu suurus

Rekursiivsetes jaga-ja-valitse algoritmide implementatsioonides on oluline jälgida, et kutsepinule on eraldatud piisavalt mälu, muul juhul võib jooksutamine ebaõnnestuda pinu ületäitumise tõttu. Enamikul aja suhtes efektiivsetel algoritmidel on siiski üsna väike rekursioonisügavus. Näiteks on võimalik kiirsortimist implementeerida nii, et see ei vaja kunagi rohkem kui $\log _{2}n$ rekursioonisügavust $n$ elemendi sortimiseks.

Pinu ületäitumist võib rekursiivsete implementatsioonide korral olla raske vältida, sest paljud kompilaatorid eeldavad, et kutsepinu on pidev mäluplokk ja osad eraldavad sellele konstantse hulga mälu. Lisaks võivad kompilaatorid pinus hoida rohkem andmeid kui on rangelt vajalik, nagu näiteks tagastusaadress, muutumatud parameetrid ja protseduuri sisemised muutujad. Seega saab pinu ületäitumise riski vähendada minimeerides rekursiivse protseduuri parameetreid ja sisemisi muutujaid või kasutades eraldi pinu struktuuri.

Baasjuhtude valimine

Iga rekursiivse algoritmi korral saab vabalt valida baasjuhud, rekursiooni lõpetamiseks otse lahendatavad väikesed alamprobleemid.

Väikseimate või lihtsaimate võimalike baasjuhtude valimine on elegantsem ja tavaliselt viib lihtsamate programmideni, sest on vaja arvestada väiksema hulga juhtudega ja neid on lihtsam lahendada. Näiteks kiirsortimise võib lõpetada, kui sisendiks on tühi loend, mispuhul on vaid üks baasjuht ja see ei vaja töötlemist.

Samas suureneb sageli efektiivsus, kui suhteliselt suurte baasjuhtude korral rekursioon lõpetada ja need juhud lahendada mitte-rekursiivelt; selline algoritm on hübriidalgoritm. See strateegia väldib rekursiivsete kutsete, mis teevad vähe või mitte üldse tööd, lisakulu ja võimaldab kasutada spetsiaalseid mitte-rekursiivseid algoritme, mis on nende kindlate baasjuhtude korral efektiivsemad.

Seega näiteks paljude teekide kiirsortimise implementatsioon lülitab ümber lihtsale tsüklipõhisele pistemeetodile (või sarnasele algoritmile), kui sorditavaid elemente on piisavalt vähe. Tuleb tähele panna, et kui tühi loend oleks ainus baasjuht, siis $n$ elemendiga loendi sortimine nõuaks $n$ kutset, mis ei tee midagi muud kui tagastavad kohe. Baasjuhtude suurendamine loenditeks kahe või vähema elemendiga eemaldab enamiku neist juhtudest ja üldisemalt baasjuhte suuremaid kui kaks kasutatakse, et vähendada ajakulu funktsioonikutsetele või pinu kasutusele.

Korduvate alamprobleemide jagamine

Osade probleemide korral võib naiivne rekursioon viia samade alamprobleemide mitu korda lahendamiseni. Sellistel juhtudel võib olla kasulik hoida alles lahendused nendele kattuvatele alamprobleemidele. Seda tehnikat nimetatakse mäluga rekursiooniks. Keerukam, aga veel efektiivsem lähenemine kattuvate alamprobleemiga probleemide lahendamiseks on dünaamiline programmeerimine.

Viited

↑ Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).
↑ Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
↑ Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
↑ M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. on the Foundations of Computer Science.
↑ Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

Välislingid

[CLR-1] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).

[2] Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.

[3] Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

[Knuth3-4] Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).

[cahob-5] M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. on the Foundations of Computer Science.

[6] Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

[1]

[2]

[3]

[4]

[5]

[6]